package main

import (
	"fmt"

	"gitee.com/wolferhua/gostudy/algorithm/utils"
)

func main() {
	numbers := utils.GetRandSlices(10, 4) // []int{3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6}
	fmt.Println("元数据：", numbers)
	HeapSort(numbers)
}

func HeapSort(arr []int) {
	length := len(arr)

	//初始化，i从最後一个父节点开始调整，构建初始堆。
	for i := length/2 - 1; i >= 0; i-- {
		// fmt.Println("==============================================")
		// fmt.Println(i, length-1)
		MaxHeapify(arr, i, length-1)
	}
	fmt.Println("构建堆以后：", arr)
	//先将第一个元素和已排好元素前一位做交换，再重新调整，直到排序完毕
	count := 0
	for i := length - 1; i > 0; i-- {
		//swap(&arr[0], &arr[i]);
		// fmt.Println("==============================================")
		// fmt.Println(i - 1)
		arr[0], arr[i] = arr[i], arr[0]
		MaxHeapify(arr, 0, i-1)
		count++

		fmt.Printf("第 %d 次调整堆后：%v\n", count, arr)
	}
	// fmt.Println(arr)

	fmt.Println("排序后：", arr)
}

func MaxHeapify(arr []int, start, end int) {
	//建立父节点指标和子节点指标
	dad := start
	son := dad*2 + 1
	for son <= end { //若子节点指标在范围内才做比较
		if son+1 <= end && arr[son] < arr[son+1] { //先比较两个子节点大小，选择最大的
			son++
		}
		if arr[dad] > arr[son] { //如果父节点大於子节点代表调整完毕，直接跳出函数
			return
		} else { //否则交换父子内容再继续子节点和孙节点比较
			// fmt.Printf("dad=%d,son=%d\n\n", dad, son)
			// fmt.Println(arr)
			arr[dad], arr[son] = arr[son], arr[dad]
			dad = son
			son = dad*2 + 1
		}
	}
}
